package com.hnlwh.sort;

import org.junit.Test;

/**
 * @program: sortingalgorithm
 * @description: 插入排序
 * @author: yuhui
 * @date: 2021-07-27 22:13
 */
public class InsertionSort {
    public static void main(String[] args) {

        /*
         * 1.通过比较current与array[preIndex]的大小 当满足不等式则执行循环体
         * 2.此时 array[preIndex+1]等于array[preIndex] 而 array[preIndex]为0
         * 3.通过 preIndex--，则让 current继续与array[preIndex]作比较（preIndex已经-1）以此类推
         * 4.再将 current 赋值为 array[preIndex+1] 由于前面--了所以这里要+1
         */
        Integer[] array = {5, 1, 35, 12, 85, 26, 30, 9999, 45, 100, 65, 51, 22, 120};
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex]) { //  1.   3.
                array[preIndex + 1] = array[preIndex]; //   2.
                preIndex--; //    3.
            }
            array[preIndex + 1] = current; //   4.
        }
        for (int arr : array) {
            System.out.print(arr + " ");
        }
    }
}